/*
https://leetcode-cn.com/problems/reverse-pairs/solution/fan-zhuan-dui-by-leetcode-solution/
 */
public class Solution493 {
    public int reversePairs(int[] nums) {
        if (nums.length==0){
            return 0;
        }
        return merge(nums,0,nums.length-1);
    }

    int merge(int[] nums,int l,int r){
        if (l==r){
            return 0;
        }
        int mid=(l+r)/2;
        int ans=0;
        ans=ans+merge(nums,l,mid);
        ans=ans+merge(nums,mid+1,r);
        int j=mid+1;
        for (int i=l;i<=mid;i++){
            while (j<=r && (long)nums[i]>2*(long)nums[j]){
                j++;
            }
            ans=ans+j-mid-1;
        }
        int[] temp=new int[r-l+1];
        int count=0;
        int i=l;
        j=mid+1;
        while (i<=mid && j<=r){
            if (nums[i]<nums[j]){
                temp[count]=nums[i];
                i++;
            }else{
                temp[count]=nums[j];
                j++;
            }
            count++;
        }
        while (i<=mid){
            temp[count]=nums[i];
            i++;
            count++;
        }
        while (j<=r){
            temp[count]=nums[j];
            j++;
            count++;
        }
        for (i=l;i<=r;i++){
            nums[i]=temp[i-l];
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution493().reversePairs(new int[]{1,3,2,3,1}));
    }
}
